package main

import (
	"fmt"
	"time"
)

// 判断坐标 (r, c) 是否在网格中
func inArea(grid [][]byte, r int, c int) bool {
	return 0 <= r && r < len(grid) && 0 <= c && c < len(grid[0])
}

// 深度遍历
func dfs(grid [][]byte, r int, c int) {
	// 判断 base case
	if !inArea(grid, r, c) {
		return
	}
	// 如果这个格子不是岛屿，直接返回
	if grid[r][c] != '1' {
		return
	}
	grid[r][c] = '2' // 将格子标记为「已遍历过」

	// 访问上、下、左、右四个相邻结点
	dfs(grid, r-1, c)
	dfs(grid, r+1, c)
	dfs(grid, r, c-1)
	dfs(grid, r, c+1)
}

func numIslands(grid [][]byte) int {
	num_islands := 0
	m := len(grid)
	n := len(grid[0])

	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == '1' {
				num_islands++
				dfs(grid, i, j)
			}
		}
	}
	return num_islands
}

func main() {
	start := time.Now()
	grid := [][]byte{
		{'1', '1', '0', '0', '0'},
		{'1', '1', '0', '0', '0'},
		{'0', '0', '1', '0', '0'},
		{'0', '0', '0', '1', '1'}}
	result := numIslands(grid)
	cost := time.Since(start)
	fmt.Println("result:", result)
	fmt.Println(cost)
}
